// 147.对链表进行插入排序
package Leetcode_Second_Brush;

public class Solution147 {
    public ListNode insertionSortList(ListNode head) {
        if (head == null)
            return null; // 如果链表为空，直接返回

        ListNode sortedHead = new ListNode(0); // 新链表的头节点
        ListNode curr = head; // 原链表中待插入的节点

        while (curr != null) {
            ListNode next = curr.next; // 暂存下一个节点

            // 在新链表中寻找插入位置的前一个节点
            ListNode prev = sortedHead;
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }

            // 插入当前节点到已排序部分
            curr.next = prev.next;
            prev.next = curr;

            curr = next; // 处理下一个节点
        }

        return sortedHead.next; // 返回新链表的头节点
    }

}
